package com.datastructure.test.traversethematrixdiagonally;

import java.util.ArrayList;

public class TraverseTheMatrixDiagonally {

    public static void main(String[] args) {
        TraverseTheMatrixDiagonally traverseTheMatrixDiagonally = new TraverseTheMatrixDiagonally();
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        int[] diagonalOrder = traverseTheMatrixDiagonally.diagonalOrder(mat);
        System.out.println(diagonalOrder);
    }

    public int[] diagonalOrder (int[][] mat) {
        // write code here
        int[] result = new int[mat.length*mat[0].length];
        ArrayList<ArrayList<Coordinate>> res = new ArrayList<>();
        ArrayList<Coordinate> list ;
        Coordinate coordinate;
        Coordinate coordinateTemp;
        int index=0;
        for(int j=0;j<mat[0].length;j++){
            list=new ArrayList<>();
            int i=0;
            int k=j;
            do{
                coordinate=new Coordinate(i,k);
                list.add(coordinate);
                i++;
                k--;
            }while (i<=mat.length-1&&k>=0);
            res.add(list);
        }
        for(int i =1;i<mat.length;i++){
            list=new ArrayList<>();
            int j=mat[0].length-1;
            int k = i;
            do{
                coordinate=new Coordinate(k,j);
                list.add(coordinate);
                k++;
                j--;
            }while (k<=mat.length-1&&j>=0);
            res.add(list);
        }
        for (int i = 0; i < res.size(); i++) {
            ArrayList<Coordinate> coordinates = res.get(i);
            if(i%2==0){
                for (int size = coordinates.size()-1; size >= 0; size--) {
                    coordinateTemp = coordinates.get(size);
                    result[index]=mat[coordinateTemp.x][coordinateTemp.y];
                    index++;
                }
            }else {
                for (Coordinate coordinate1 : coordinates) {
                    result[index]=mat[coordinate1.x][coordinate1.y];
                    index++;
                }
            }
        }
        return result;
    }
}

class Coordinate {
    public int x;
    public int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
